public class Num337 {
    public int rob(TreeNode root) {
        int[] result = robInternal(root);
        return Math.max(result[0], result[1]);
    }

    public int[] robInternal(TreeNode root) {
        //空节点偷不了
        if (root == null) return new int[2];
        int[] res = new int[2];

        //偷左边
        int[] robLeft = robInternal(root.left);
        //偷右边
        int[] robRight = robInternal(root.right);

        //本节点要是不偷的话,最大值就是偷左右两边得
        res[0] = Math.max(robLeft[0], robLeft[1]) +Math.max(robRight[0], robRight[1]);
        //本节点偷,最大值就是左右不偷加上本节点的值
        res[1] = robLeft[0] +robRight[0] +root.val;

        return res;
    }
}
